The present invention relates to posterior probabilities for discrete hidden states. In particular, the present invention relates to forward-backward recursion for determining posterior probabilities.
In recognition tasks, such as speech recognition, facial recognition, speaker recognition, and hand writing recognition, it is common to need to identify a sequence of discrete hidden states from a sequence of observed values. Typically, each observed value is associated with a time frame t and identifying the sequence of discrete hidden states involves selecting one hidden state s out of a set of N possible states S at each time frame.
To identify the sequence of hidden states, a posterior probability p(sn,t|o1T) is often determined for each possible state sn in each time frame t. One technique for determining these posterior probabilities is known as forward-backward recursion. In the forward-backward recursion, a forward recursion is first performed in which a score for a state in a given frame is based upon scores for each of the states in the preceding frame. Thus, the scores are built in a left-right manner in which scores for the first frame must be determined before scores for the subsequent frames. During the backward recursion, the score for a state in a frame is dependent on the score of all of the states in the next frame. Thus, the states are scored from right-to-left. The scores from the forward recursion and the backward recursion for a given state in a given time frame are then combined to give the posterior probability for that state in that time frame.
In the past, the forward-backward recursion has required that three sets of values be determined for each state at each time frame. Specifically, a forward recursion score, a backward recursion score and a posterior probability has been determined for each state at each time frame. For systems that have a large number of states, for instance systems that use 25 million states in each time frame, this prior art technique has required a large amount of memory. For example, under the prior art, for 25 million states and a thousand frames of data, 75 billion values have been stored consisting of 25 billion forward recursion values, 25 billion backward recursion values, and 25 billion posterior probabilities. This large memory requirement is undesirable. As such, a more efficient method of performing forward-backward recursion to determine posterior probabilities is needed.